Turmites

A Formiga de Langton é um exemplo de uma Turmite, uma Máquina de Turing bidimensional. Se isso não significa nada para você, não se preocupe! A Formiga de Langton é um sistema pequeno governado por regras simples.

1. Introdução

Em sua forma mais simples, Langton's Ant funciona da seguinte forma:

  • Comece uma "formiga" voltada para o norte ("para cima") no centro de uma grade bidimensional ((grid_size // 2, grid_size // 2)), com todas as células coloridas em branco.
  • Ande vários passos. Em cada passo:
    • A formiga muda a cor da célula em que se encontra (branco ⟶ preto e preto ⟶ branco)
    • A formiga avança uma célula (na direção para a qual estava voltada)
    • A formiga gira no lugar de acordo com as seguintes regras:
      • Se a célula em que a formiga acabou de entrar for branca, ela vira 90 graus para a direita.
      • Se a célula em que a formiga acabou de entrar for preta, ela vira 90 graus para a esquerda. Curiosamente, embora as regras que governam a evolução da formiga sejam muito simples, elas podem levar a um comportamento emergente complicado (você pode ler sobre isso no link da Wikipedia acima).

2) Exercício

Embora a Formiga de Langton seja interessante por si só, examinaremos uma versão ligeiramente estendida neste exercício. Em vez de apenas preto e branco, permitiremos que as células da grade sejam coloridas arbitrariamente (usaremos números para representar a cor de cada célula, em vez de nomes como "preto" e "branco").

Também variaremos as regras pelas quais a formiga decide em que direção virar. Usaremos uma seqüência de caracteres "L" e "R" para representar as regras pelas quais a formiga deve girar. O sistema simples acima pode ser simplificado pela string "RL"; se a formiga observar a cor 0, ela irá virar para a direita (o caractere de índice 0 na string é "R"), e se ela observar a cor 1, ela irá virar para a esquerda (o caractere de índice 1 na string é "L"). No entanto, observe que não estamos limitados a apenas duas cores e, portanto, podemos ter regras mais complicadas como "RLRR", que diz à formiga para virar à direita quando vê as cores 0, 2 ou 3, e à esquerda quando vê a cor 1.

O procedimento que vamos realmente modelar é o seguinte:

  • Comece uma "formiga" voltada para o norte ("para cima") no centro de uma grade bidimensional de tamanho size, com todas as células coloridas zero (0).
  • Dê vários passos. Para cada passo:
    • A formiga muda a cor da célula em que está incrementando a cor em 1, mas dando a volta com base no número total de cores no sistema (em um sistema de três cores, por exemplo, 0 vai para 1, 1 vai para 2 e 2 vai para 0).
    • A formiga avança uma célula (na direção para a qual estava voltada)
    • A formiga gira no lugar com base na cor da célula que acabou de entrar, de acordo com as regras, que são especificadas como uma string da forma explicada acima.

Escreva uma função chamada run_langton(rules, size) que simula a evolução de um sistema descrito acima em uma grade size-por-size. Observe que sua formiga deve começar na célula central voltada para cima. Sua função deve retornar uma tupla (count, grid), onde count é o número de passos que o sistema dá até que a formiga saia da grade (incluindo o passo que levou a formiga para fora da grade), e grid é uma lista de listas contendo inteiros, representando a coloração final da grade. Por exemplo, a grade colorida como:

+ --- + --- +
|  1  |  0  |
+ --- + --- +
|  0  |  0  |
+ --- + --- +

é representado pela seguinte lista de listas:

[[1,0], [0,0]]

Dica: você precisará de uma maneira de representar a posição da formiga, incluindo o ângulo, para saber como ajustar para o movimento da formiga "para frente".

Dica: você pode achar mais fácil começar implementando a especificação original da Formiga de Langton, na qual existem apenas duas "cores" possíveis no mundo (1 e 0), e a formiga vira à direita ao entrar em um quadrado de cor 1, e à esquerda ao entrar em um quadrado de cor 0. Depois de implementar isso, pense em como você pode estendê-lo para o caso mais geral descrito acima.

Submissão

Quando estiver pronto (depois de ter simulado manualmente e testado em sua própria máquina e estiver convencido de que seu programa fará a coisa certa), faça upload do seu arquivo Python no Problema 5.1 no Gradescope. Lembre de nomear seu arquivo p5_1.py.